#define _CRT_SECURE_NO_WARNINGS
typedef char STDataType;

typedef struct stack {
    STDataType* a;
    int capacity;
    int size;
} Stack;

void StackInit(Stack* ps) {
    ps->a = NULL;
    ps->capacity = ps->size = 0;
}

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->size == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tmp =
            (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (tmp) {
            ps->a = tmp;
        }
        else {
            perror("realloc fail");
        }
    }
    ps->a[ps->size] = data;
    ps->size++;
}

void StackPop(Stack* ps) {
    assert(ps);
    assert(ps->size > 0);
    ps->size--;
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->size;
}
STDataType StackTop(Stack* ps) {
    assert(ps);

    int size = ps->size - 1;
    return ps->a[size];
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    if (StackSize(ps) == 0) {
        return true;
    }
    else {
        return false;
    }
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

bool isValid(char* s) {
    Stack st;
    StackInit(&st);


    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{') {
            StackPush(&st, *s);
        }
        else {
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }
            char left = StackTop(&st);
            StackPop(&st);

            if ((left == '(' && *s != ')') || (left == '{' && *s != '}') ||
                (left == '[' && *s != ']')) {
                StackDestroy(&st);
                return false;
            }
        }
        ++s;
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}


int main() {


    return 0;
}